import java.util.Arrays;

/**
 * @author WangTianyi
 * @create 2021-12-03 21:53
 */
public class HeapSort {
    public static void main(String[] args) {
        double[] array1 = new double[]{46, 74, 16, 53, 14, 26, 40, 53, 86, 65, 27, 34};
        double[] array2 = new double[]{46, 74, 16, 53, 14, 26, 40, 53, 86, 65, 27, 34};
        minHeapSort(array1);
        System.out.println(Arrays.toString(array1));
        maxHeapSort(array2);
        System.out.println(Arrays.toString(array2));
    }

    public static void minHeapSort(double[] array){

        //1.创建初始小根堆
        for (int i = (array.length-1 - 1)/2; i >= 0; i--) {
            minSiftDown(array, i, array.length-1);
        }

        //2.每次把堆顶元素取出来放到最后,把最后放在下标0处，并进行堆调整（导致该排序为从大到小排序）
        int end = array.length;
        for (int i = 0; i < array.length-1; i++) {
            end--;
            swap(array, 0, end);
            minSiftDownPro(array, 0, end-1);
//            System.out.println("test: "+Arrays.toString(array));
        }
    }

    public static void maxHeapSort(double[] array){
        //1.创建初始大根堆
        for (int i = (array.length-1 - 1)/2; i >= 0; i--) {
            maxSiftDownPro(array, i, array.length-1);

        }

        //2.每次把堆顶元素取出来放到最后,把最后放在下标0处，并进行堆调整（导致该排序为从小到大排序）
        int end = array.length;
        for (int i = 0; i < array.length-1; i++) {
            end--;
            swap(array, 0, end);
            maxSiftDown(array, 0, end-1);
//            System.out.println("test: "+Arrays.toString(array));
        }
    }

    public static void minSiftDown(double[] array, int begin, int end){
        int i = begin;
        int j = 2*i+1;
        while(j<=end){
            if(j<end && array[j+1]<array[j]){
                j+=1;
            }
            if(array[j]<array[i]){
                swap(array, i, j);
            }else{
                break;
            }
            i = j;
            j = 2*i+1;
        }
    }

    public static void minSiftDownPro(double[] array, int begin, int end){
        double tempElem = array[begin];
        int i = begin;
        int j = i*2+1;
        while(j<=end){
            if(j<end && array[j+1]<array[j]){
                j+=1;
            }
            if(array[j]<tempElem){
                array[i] = array[j];
            }else{
                break;
            }
            i = j;
            j = 2*i+1;
        }
        array[i] = tempElem;
    }

    public static void maxSiftDown(double[] array, int begin, int end){
        int i = begin;
        int j = i*2+1;
        while(j<=end){
            if(j<end && array[j+1]>array[j]){
                j+=1;
            }
            if(array[j]>array[i]){
                swap(array, i, j);
            }else{
                break;
            }
            i = j;
            j = i*2+1;
        }
    }

    public static void maxSiftDownPro(double[] array, int begin, int end){
        int i = begin;
        int j = 2*i + 1;
        double tempElem = array[i];
        while(j<=end){
            if(j<end && array[j+1]>array[j]){
                j+=1;
            }
            if(array[j] > tempElem){
                array[i] = array[j];
            }else{
                break;
            }
            i = j;
            j = 2*i+1;
        }
        array[i] = tempElem;
    }

    public static void swap(double[] array, int indexi, int indexj){
        double temp = array[indexi];
        array[indexi] = array[indexj];
        array[indexj] = temp;
    }
}
